// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class ReverseNodesInkGroup {
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){ // 空结点或者只有一个结点直接返回
            return head;
        }
        ListNode start = head;
        ListNode end = teamEnd(start,k);
        if(end == null) {
            return head;
        }
        head = end;
        reverse(start,end);
        ListNode lastTeamEnd = start;

        while (lastTeamEnd.next != null) {
            ListNode lastStart = lastTeamEnd.next;
            ListNode lastEnd = teamEnd(lastStart,k);
            if(lastEnd == null) {
                return head;
            }
            reverse(lastStart,lastEnd);
            lastTeamEnd.next = lastEnd;
            lastTeamEnd = lastStart;
        }
        return head;
    }

    public static ListNode teamEnd(ListNode start, int k) {
        while(--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    public static void reverse(ListNode start , ListNode end) {
       end = end.next;
       ListNode cur = start, prev = null, next = null;
       while(cur != end){
           next = cur.next;
           cur.next = prev;
           prev = cur;
           cur = next;
       }
       start.next = end;
    }
}
